package leetCode.secondWeek;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Code_17 {
  public static Character[][] tmp =
      new Character[][] {
        {},
        {},
        {'a', 'b', 'c'},
        {'d', 'e', 'f'},
        {'g', 'h', 'i'},
        {'j', 'k', 'l'},
        {'m', 'n', 'o'},
        {'p', 'q', 'r', 's'},
        {'t', 'u', 'v'},
        {'w', 'x', 'y', 'z'}
      };
  public static List<String> res = new LinkedList<>();

  public List<String> letterCombinations(String digits) {
    if (digits.length() == 0) {
      return new LinkedList<>();
    }
    List<Integer> digitsIntArr = new LinkedList<>();
    for (int i = digits.length() - 1; i >= 0; i--) {
      digitsIntArr.add(Integer.parseInt(String.valueOf(digits.charAt(i))));
    }
    carry("", digitsIntArr);
    List<String> returnData = new LinkedList<>(res);
    res = new LinkedList<>();
    return returnData;
  }

  public static void carry(String tmpStr, List<Integer> queue) {
    if (queue.isEmpty()) {
      res.add(tmpStr);
      return;
    }
    int firstQue = queue.get(queue.size() - 1);
    queue.remove(queue.size() - 1);
    for (int i = 0; i < tmp[firstQue].length; i++) {
      carry(tmpStr + tmp[firstQue][i], queue);
    }
    queue.add(firstQue);
  }
}
